package com.ai.zuochengyun.phase01.class04;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 安排最多会议宣讲
 */
public class Code02_BestArrange {

    public static void main(String[] args) {
        int testTimes = 10000;
        int arrLen = 6;
        for (int i = 0; i < testTimes; i++) {
            Meeting[] m1 = new Meeting[arrLen];
            for (int j = 0; j < arrLen; j++) {
                int a = (int) (Math.random() * 24);
                int b = (int) (Math.random() * 24);
                int start = Math.min(a, b);
                int end = Math.max(a, b);
                if (start == end && start == 0) {
                    end = 1;
                }
                if (start == end && start == 23) {
                    start = 22;
                }
                m1[j] = new Meeting(start, end);
            }
            Meeting[] m2 = new Meeting[arrLen];
            System.arraycopy(m1, 0, m2, 0, m1.length);
            Meeting[] m3 = new Meeting[arrLen];
            System.arraycopy(m1, 0, m3, 0, m1.length);

            if (bestArrange1(m2) != bestArrange2(m3)) {
                for (int j = 0; j < m1.length; j++) {
                    System.out.print("[" + m1[j].start + "-" + m1[j].end + "]");
                }
                System.out.println();
                System.out.println("Oops");
                break;
            }
        }
        System.out.println("Finish!");
    }

    /**
     * 暴力解法
     *
     * @param meetings
     * @return
     */
    private static int bestArrange1(Meeting[] meetings) {
        if (meetings == null || meetings.length == 0) {
            return 0;
        }
        return process(meetings, 0, -1);
    }

    private static int process(Meeting[] meetings, int done, int timeLine) {
        if (meetings.length == 0) {
            return done;
        }
        int ans = done;
        for (int i = 0; i < meetings.length; i++) {
            if (meetings[i].start >= timeLine) {
                // 将当前会议移除，重新生成一个新数组
                Meeting[] next = copyButExceptOne(meetings, i);
                ans = Math.max(ans, process(next, done + 1, meetings[i].end));
            }
        }
        return ans;
    }

    private static Meeting[] copyButExceptOne(Meeting[] meetings, int index) {
        Meeting[] ans = new Meeting[meetings.length - 1];
        int ansIndex = 0;
        for (int i = 0; i < meetings.length; i++) {
            if (i == index) {
                continue;
            }
            ans[ansIndex++] = meetings[i];
        }
        return ans;
    }

    /**
     * 排序解法
     *
     * @param meetings
     * @return
     */
    private static int bestArrange2(Meeting[] meetings) {
        if (meetings == null || meetings.length == 0) {
            return 0;
        }
        Arrays.sort(meetings, new MyComparator());
        // 当前时间点
        int timeLine = -1;
        int ans = 0;
        // 依次遍历每一个会议，结束时间越早的越先遍历
        for (Meeting m : meetings) {
            // 会议的开始时间 如果 大于等于 当前时间点，那么就可以安排
            if (m.start >= timeLine) {
                ans++;
                // 当前会议的结束时间作为下一次的起始时间点
                timeLine = m.end;
            }
        }
        return ans;
    }

    /**
     * 比较器
     */
    private static class MyComparator implements Comparator<Meeting> {

        /**
         * 结束时间越早的排在前
         *
         * @param o1 the first object to be compared.
         * @param o2 the second object to be compared.
         * @return
         */
        @Override
        public int compare(Meeting o1, Meeting o2) {
            return (o1.end - o2.end) == 0 ? o1.start - o2.start : o1.end - o2.end;
        }
    }

    private static class Meeting {
        public int start;
        public int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

}
